//二维费用背包问题
//f[n][u][v]=max{f[n-1][u-w1[n]][v-w2[n]]},u和v倒推可以省去第一维n
import java.util.Arrays;

public class Solution805 {
    public boolean splitArraySameAverage(int[] nums) {
        int t=nums.length/2;
        int sum= Arrays.stream(nums).sum();
        for (int i=1;i<=t;i++){
            if (sum*i%nums.length==0){
                int target=sum*i/nums.length;
                boolean[][] f=new boolean[t+1][target+1];
                f[0][0]=true;
                for (int j=0;j<nums.length;j++){
                    for (int k=i;k>=1;k--){
                        for (int l=target;l>=0;l--){
                            if (l-nums[j]>=0) {
                                f[k][l] = f[k][l] || f[k - 1][l - nums[j]];
                            }
                        }
                    }
                }
                if (f[i][target]){
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(new Solution805().splitArraySameAverage(new int[]{17,3,7,12,1}));
    }
}
